package com.acwing.partition9;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/12/1 10:49
 */
public class AC853有边数限制的最短路 {

    private static final int INF = 0x3f3f3f3f;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]), k = Integer.parseInt(s[2]);
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split(" ");
            int x = Integer.parseInt(s[0]), y = Integer.parseInt(s[1]), z = Integer.parseInt(s[2]);
            edges[i][0] = x;
            edges[i][1] = y;
            edges[i][2] = z;
        }
        int ans = bellmanFord(n, edges, k, 1, n);
        if (ans == -2) writer.write("impossible\n");
        else writer.write(ans + "\n");
        writer.flush();
    }

    private static int bellmanFord(int n, int[][] edges, int k, int start, int end) {
        int[] distance = new int[n + 1];
        for (int i = 1; i <= n; i++) distance[i] = INF;
        distance[start] = 0;
        for (int i = 0; i < k; i++) {
            int[] distanceClone = distance.clone();
            for (int[] edge : edges) {
                distance[edge[1]] = Math.min(distance[edge[1]], distanceClone[edge[0]] + edge[2]);
            }
        }
        return distance[end] > INF / 2 ? -2 : distance[end];
    }
}
